#include <iostream>

void ShellSort(int* a, int n)
{
    int gap=n;
    while(gap>1)
    {
        gap/=2;
        for(int i=0;i<n-gap;i+=gap)
        {
            int end=i-gap;
            int temp=a[end+gap];
            while(end>=0)
            {
                if(a[end]>temp)
                {
                    a[end+gap]=a[end];
                    end-=gap;
                }
                else
                {
                    break;
                }
            }
            a[end+gap]=temp;
        }
    }
}

int main()
{
    int a[10]={5,3,6,9,7,1,0,2,4,10};
    ShellSort(a,10);
    for(int i=0;i<10;i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
    return 0;
}